package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.shortestpath;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import lombok.AccessLevel;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;

/**
 * <h1>Bellman-Ford 最短路径算法</h1>
 * <p>
 *     <h2>简介</h2>
 *     <p>
 *          由R.Bellman和L.Ford在20世纪50年代末期发明的算法.<br>
 *          在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环，以下算法能够解决其中的单点最短路径问题：将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大。以任意顺序放松有向图的所有边，重复V轮。
 *     </p>
 *     <h2>证明</h2>
 *     <p>
 *         主要证明的方法是<b>数学归纳法</b><br>
 *         于从s可达的任意顶点t，考虑从s到t的一条最短路径：v0→v1→...→vk，其中v0等于s，vk等于t。因为负权重环是不可达的，这样的路径是存在的且k不会大于V-1。
 *         我们会通过归纳法证明算法在第i轮之后能够得到s到vi的最短路径。
 *         最简单的情况（i=0）很容易。假设对于i命题成立，那么s到vi的最短路径即为v0→v1→...→vi，distTo[vi]就是这条路径的长度。
 *         现在，我们在第i轮中放松所有的顶点，包括vi，因此distTo[vi+1]不会大于distTo[vi]与边vi→vi+1的权重之和。
 *         在第i轮放松之后，distTo[vi+1]必然等于distTo[vi]与边vi→vi+1的权重之和。
 *         它不可能更大，因为在第i轮中放松了所有顶点，包括vi；
 *         它也不可能更小，因为它就是路径v0→v1→...→vi+1的长度，也就是最短路径了。
 *         因此，在i+1轮之后算法能够得到从s到vi+1的最短路径
 *     </p>
 * </p>
 * <p>
 *     <h2>使用队列优化</h2>
 *     <p>
 *         在原始的BellmanFordSP算法中，每轮放松都会放松所有顶点的所有边。其实从第二轮开始，只放松有关联的节点就可以了。
 *     </p>
 *     <h2>关于负权重环</h2>
 *     <p>
 *         在有负权重的环下，是没有最短路径的。经过证明上述证明，可以确定在V-1轮Relax操作之后，最短路径算法就应该执行完毕，如果还没有结束，说明必然有环存在。可以在结果中把环便利出来。
 *     </p>
 * </p>
 */

@Setter(AccessLevel.PRIVATE)
@Accessors(chain = true)
public class BellmanFordSP<T> {


    private Graph<T> graph;
    private Vertex<T> source;
    //队列
    private Deque<Vertex<T>> vertexDeque = new LinkedList<>();
    //指向顶点的边
    private Map<Vertex<T>, Edge<T>> edgeTo ;
    //到指定边的权重
    private Map<Vertex<T>, Double> priority ;

    private int relaxCount = 0;
    @Getter
    private boolean hasNegativeCycle = false;
    @Getter
    private List<Edge<T>> negativeCycleEdge = null;










    public double distTo(T target) {
        return priority.get(Vertex.create(target));
    }

    public boolean hasPathTo(T target){
        return this.edgeTo.containsKey(Vertex.create(target));
    }

    public Iterable<Edge<T>> pathTo(T target){

        //路径

        Deque<Edge<T>> result = new LinkedList<>();

        for (Edge<T> edge = this.edgeTo.get(Vertex.create(target));edge!=null;edge=edgeTo.get(edge.getFrom())) {
            result.push(edge);
        }

        return result;
    }















    private BellmanFordSP<T> init(){

        //设置所有顶点的权重为最大，起点的权重为0

        graph.getVertices().forEach((key,value)->priority.put(value,Double.MAX_VALUE));
        priority.put(source, 0.0d);

        //起点加入队列中

        vertexDeque.offer(source);
        //队列中有数据，并且
        while (!hasNegativeCycle&&!vertexDeque.isEmpty()){
            relax(vertexDeque.poll());
        }
        return this;
    }


    private void relax(Vertex<T> vertex) {
        vertex.getNext().forEach(edge->{
            if(priority.get(edge.getTo()).compareTo(priority.get(vertex)+edge.getWeight())>0){
                priority.put(edge.getTo(), priority.get(vertex) + edge.getWeight());
                if (!vertexDeque.contains(edge.getTo())){
                    vertexDeque.offer(edge.getTo());
                }
                //校验负环
                if(relaxCount++%this.graph.getVertices().size()==0){
                    checkNegativeCycle();
                }
                ;
            }
        });
    }


    //检测是否有负环
    private void checkNegativeCycle() {
        CycleCheck<T> cycleCheck = CycleCheck.create(this);
        this.hasNegativeCycle = cycleCheck.hasCycle;
        if(this.hasNegativeCycle){
            System.out.println("检测到负环");
        }
        this.negativeCycleEdge = cycleCheck.cycleList;
    }



    public static <T> BellmanFordSP<T> create(Graph<T> graph,T source){
        int size = graph.getVertices().size();
        return new BellmanFordSP<T>()
                .setGraph(graph)
                .setEdgeTo(new HashMap<>(size))
                .setPriority(new HashMap<>(size))
                .setSource(graph.getVertices().get(Vertex.create(source)))
                .init();


    }

    /**
     * 环路检测
     */
    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private static class CycleCheck<T>{
        private BellmanFordSP<T> sp;

        private boolean hasCycle;

        private List<Edge<T>> cycleList = new LinkedList<>();



        private Set<Vertex<T>> onstack = new HashSet<>();


        private Deque<Edge<T>> edges = new LinkedList<>();

        private Vertex<T> cycleVertex = null;

        private CycleCheck<T> cycleCheck(){

            this.sp.edgeTo.forEach((key,value)->dfs(key));
            if(hasCycle){
                //计算环路

                Edge<T> current = null;
                do {
                     current = edges.pop();
                    this.cycleList.add(current);
                }
                while (!Objects.equals(current.getTo(), cycleVertex));
            }
            return this;
        }
        //遍历顶点
        private void dfs(Vertex<T> vertex){
            //退出条件

            if (hasCycle) {
                return;
            }
            Edge<T> edge = sp.edgeTo.get(vertex);
            if(edge!=null){
                onstack.add(vertex);//记录在栈中
                this.edges.push(edge);
                if(onstack.contains(edge.getFrom())){
                    this.hasCycle = true;
                    this.cycleVertex = vertex;
                    return;
                }
                dfs(edge.getFrom());
                onstack.remove(vertex);//删除在栈记录
                this.edges.pop();
            }


        }
        public static final <T> CycleCheck<T> create(BellmanFordSP<T> sp){
            return new CycleCheck<T>().setSp(sp).cycleCheck();
        }

    }

}
